home *** CD-ROM | disk | FTP | other *** search
/ Acorn RISC PD-CD 1 / Acorn RISC PD-CD 1.iso / utilities / _graphics / graphics / _jpeg / c / jchuff < prev    next >
Encoding:
Text File  |  1991-10-28  |  19.3 KB  |  690 lines
  1. /*
  2.  * jchuff.c
  3.  *
  4.  * Copyright (C) 1991, Thomas G. Lane.
  5.  * This file is part of the Independent JPEG Group's software.
  6.  * For conditions of distribution and use, see the accompanying README file.
  7.  *
  8.  * This file contains Huffman entropy encoding routines.
  9.  * These routines are invoked via the methods entropy_encode,
  10.  * entropy_encoder_init/term, and entropy_optimize.
  11.  */
  12.  
  13. #include "jinclude.h"
  14.  
  15.  
  16. /* Static variables to avoid passing 'round extra parameters */
  17.  
  18. static compress_info_ptr cinfo;
  19.  
  20. static INT32 huff_put_buffer;   /* current bit-accumulation buffer */
  21. static int huff_put_bits;       /* # of bits now in it */
  22.  
  23. static char * output_buffer;    /* output buffer */
  24. static int bytes_in_buffer;
  25.  
  26.  
  27.  
  28. LOCAL void
  29. fix_huff_tbl (HUFF_TBL * htbl)
  30. /* Compute derived values for a Huffman table */
  31. {
  32.   int p, i, l, lastp, si;
  33.   char huffsize[257];
  34.   UINT16 huffcode[257];
  35.   UINT16 code;
  36.   
  37.   /* Figure 7.3.5.4.2.1: make table of Huffman code length for each symbol */
  38.   /* Note that this is in code-length order. */
  39.  
  40.   p = 0;
  41.   for (l = 1; l <= 16; l++) {
  42.     for (i = 1; i <= htbl->bits[l]; i++)
  43.       huffsize[p++] = l;
  44.   }
  45.   huffsize[p] = 0;
  46.   lastp = p;
  47.   
  48.   /* Figure 7.3.5.4.2.2: generate the codes themselves */
  49.   /* Note that this is in code-length order. */
  50.   
  51.   code = 0;
  52.   si = huffsize[0];
  53.   p = 0;
  54.   while (huffsize[p]) {
  55.     while (huffsize[p] == si) {
  56.       huffcode[p++] = code;
  57.       code++;
  58.     }
  59.     code <<= 1;
  60.     si++;
  61.   }
  62.   
  63.   /* Figure 7.3.5.4.2.3: generate encoding tables */
  64.   /* These are code and size indexed by symbol value */
  65.  
  66.   for (p = 0; p < lastp; p++) {
  67.     htbl->ehufco[htbl->huffval[p]] = huffcode[p];
  68.     htbl->ehufsi[htbl->huffval[p]] = huffsize[p];
  69.   }
  70.   
  71.   /* Figure 13.4.2.3.1: generate decoding tables */
  72.  
  73.   p = 0;
  74.   for (l = 1; l <= 16; l++) {
  75.     if (htbl->bits[l]) {
  76.       htbl->valptr[l] = p;      /* huffval[] index of 1st sym of code len l */
  77.       htbl->mincode[l] = huffcode[p]; /* minimum code of length l */
  78.       p += htbl->bits[l];
  79.       htbl->maxcode[l] = huffcode[p-1]; /* maximum code of length l */
  80.     } else {
  81.       htbl->maxcode[l] = -1;
  82.     }
  83.   }
  84. }
  85.  
  86.  
  87. /* Outputting bytes to the file */
  88.  
  89. LOCAL void
  90. flush_bytes (void)
  91. {
  92.   if (bytes_in_buffer)
  93.     (*cinfo->methods->entropy_output) (cinfo, output_buffer, bytes_in_buffer);
  94.   bytes_in_buffer = 0;
  95. }
  96.  
  97.  
  98. #define emit_byte(val)  ((bytes_in_buffer >= JPEG_BUF_SIZE ? \
  99.                                 (flush_bytes(), 0) : 0), \
  100.                          output_buffer[bytes_in_buffer] = (val), \
  101.                          bytes_in_buffer++)
  102.  
  103.  
  104.  
  105. /* Outputting bits to the file */
  106.  
  107. /* Only the right 24 bits of huff_put_buffer are used; the valid bits are
  108.  * left-justified in this part.  At most 16 bits can be passed to emit_bits
  109.  * in one call, and we never retain more than 7 bits in huff_put_buffer
  110.  * between calls, so 24 bits are sufficient.
  111.  */
  112.  
  113. LOCAL void
  114. emit_bits (UINT16 code, int size)
  115. {
  116.   /* This routine is heavily used, so it's worth coding tightly. */
  117.   register INT32 put_buffer = code;
  118.   register int put_bits = huff_put_bits;
  119.  
  120.   put_buffer &= (((INT32) 1) << size) - 1; /* Mask off any excess bits in code */
  121.   
  122.   put_bits += size;             /* new number of bits in buffer */
  123.   
  124.   put_buffer <<= 24 - put_bits; /* align incoming bits */
  125.  
  126.   put_buffer |= huff_put_buffer; /* and merge with old buffer contents */
  127.   
  128.   while (put_bits >= 8) {
  129.     int c = (int) ((put_buffer >> 16) & 0xFF);
  130.     
  131.     emit_byte(c);
  132.     if (c == 0xFF) {            /* need to stuff a zero byte? */
  133.       emit_byte(0);
  134.     }
  135.     put_buffer <<= 8;
  136.     put_bits -= 8;
  137.   }
  138.  
  139.   huff_put_buffer = put_buffer; /* Update global variables */
  140.   huff_put_bits = put_bits;
  141. }
  142.  
  143.  
  144. LOCAL void
  145. flush_bits (void)
  146. {
  147.   emit_bits((UINT16) 0x7F, 7);  /* fill any partial byte with ones */
  148.   huff_put_buffer = 0;          /* and reset bit-buffer to empty */
  149.   huff_put_bits = 0;
  150. }
  151.  
  152.  
  153.  
  154. /* Encode a single block's worth of coefficients */
  155. /* Note that the DC coefficient has already been converted to a difference */
  156.  
  157. LOCAL void
  158. encode_one_block (JBLOCK block, HUFF_TBL *dctbl, HUFF_TBL *actbl)
  159. {
  160.   register INT32 temp;
  161.   register int nbits;
  162.   register int k, r, i;
  163.   
  164.   /* Encode the DC coefficient difference per section 7.3.5.1 */
  165.   
  166.   /* Find the number of bits needed for the magnitude of the coefficient */
  167.   temp = block[0];
  168.   if (temp < 0) temp = -temp;
  169.   
  170.   nbits = 0;
  171.   while (temp) {
  172.     nbits++;
  173.     temp >>= 1;
  174.   }
  175.   
  176.   /* Emit the Huffman-coded symbol for the number of bits */
  177.   emit_bits(dctbl->ehufco[nbits], dctbl->ehufsi[nbits]);
  178.   
  179.   /* If positive, emit nbits low order bits; */
  180.   /* if negative, emit nbits low order bits of value-1 */
  181.   if ((temp = block[0]) < 0)
  182.     temp--;
  183.   
  184.   emit_bits((UINT16) temp, nbits);
  185.   
  186.   /* Encode the AC coefficients per section 7.3.5.2 */
  187.   
  188.   r = 0;                        /* r = run length of zeros */
  189.   
  190.   for (k = 1; k < DCTSIZE2; k++) {
  191.     if ((temp = block[k]) == 0) {
  192.       r++;
  193.     } else {
  194.       /* if run length > 15, must emit special run-length-16 codes (0xF0) */
  195.       while (r > 15) {
  196.         emit_bits(actbl->ehufco[0xF0], actbl->ehufsi[0xF0]);
  197.         r -= 16;
  198.       }
  199.       
  200.       /* Find the number of bits needed for the magnitude of the coefficient */
  201.       if (temp < 0) temp = -temp;
  202.  
  203.       nbits = 1;                /* there must be at least one 1 bit */
  204.       while (temp >>= 1)
  205.         nbits++;
  206.       
  207.       /* Emit Huffman symbol for run length / number of bits */
  208.       i = (r << 4) + nbits;
  209.       emit_bits(actbl->ehufco[i], actbl->ehufsi[i]);
  210.       
  211.       /* If positive, emit nbits low order bits; */
  212.       /* if negative, emit nbits low order bits of value-1 */
  213.       if ((temp = block[k]) < 0)
  214.         temp--;
  215.       
  216.       emit_bits((UINT16) temp, nbits);
  217.       
  218.       r = 0;
  219.     }
  220.   }
  221.  
  222.   /* If the last coef(s) were zero, emit an end-of-block code */
  223.   if (r > 0)
  224.     emit_bits(actbl->ehufco[0], actbl->ehufsi[0]);
  225. }
  226.  
  227.  
  228.  
  229. /*
  230.  * Initialize for a Huffman-compressed scan.
  231.  * This is invoked after writing the SOS marker.
  232.  * The pipeline controller must establish the entropy_output method pointer
  233.  * before calling this routine.
  234.  */
  235.  
  236. METHODDEF void
  237. huff_init (compress_info_ptr xinfo)
  238. {
  239.   short ci;
  240.   jpeg_component_info * compptr;
  241.  
  242.   /* Initialize static variables */
  243.   cinfo = xinfo;
  244.   huff_put_buffer = 0;
  245.   huff_put_bits = 0;
  246.  
  247.   /* Initialize the output buffer */
  248.   output_buffer = (char *) (*cinfo->emethods->alloc_small)
  249.                                 ((size_t) JPEG_BUF_SIZE);
  250.   bytes_in_buffer = 0;
  251.  
  252.   for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
  253.     compptr = cinfo->cur_comp_info[ci];
  254.     /* Make sure requested tables are present */
  255.     if (cinfo->dc_huff_tbl_ptrs[compptr->dc_tbl_no] == NULL ||
  256.         cinfo->ac_huff_tbl_ptrs[compptr->ac_tbl_no] == NULL)
  257.       ERREXIT(cinfo->emethods, "Use of undefined Huffman table");
  258.     /* Compute derived values for Huffman tables */
  259.     /* We may do this more than once for same table, but it's not a big deal */
  260.     fix_huff_tbl(cinfo->dc_huff_tbl_ptrs[compptr->dc_tbl_no]);
  261.     fix_huff_tbl(cinfo->ac_huff_tbl_ptrs[compptr->ac_tbl_no]);
  262.     /* Initialize DC predictions to 0 */
  263.     cinfo->last_dc_val[ci] = 0;
  264.   }
  265.  
  266.   /* Initialize restart stuff */
  267.   cinfo->restarts_to_go = cinfo->restart_interval;
  268.   cinfo->next_restart_num = 0;
  269. }
  270.  
  271.  
  272. /*
  273.  * Emit a restart marker & resynchronize predictions.
  274.  */
  275.  
  276. LOCAL void
  277. emit_restart (compress_info_ptr cinfo)
  278. {
  279.   short ci;
  280.  
  281.   flush_bits();
  282.  
  283.   emit_byte(0xFF);
  284.   emit_byte(RST0 + cinfo->next_restart_num);
  285.  
  286.   /* Re-initialize DC predictions to 0 */
  287.   for (ci = 0; ci < cinfo->comps_in_scan; ci++)
  288.     cinfo->last_dc_val[ci] = 0;
  289.  
  290.   /* Update restart state */
  291.   cinfo->restarts_to_go = cinfo->restart_interval;
  292.   cinfo->next_restart_num++;
  293.   cinfo->next_restart_num &= 7;
  294. }
  295.  
  296.  
  297. /*
  298.  * Encode and output one MCU's worth of Huffman-compressed coefficients.
  299.  */
  300.  
  301. METHODDEF void
  302. huff_encode (compress_info_ptr cinfo, JBLOCK *MCU_data)
  303. {
  304.   short blkn, ci;
  305.   jpeg_component_info * compptr;
  306.   JCOEF temp;
  307.  
  308.   /* Account for restart interval, emit restart marker if needed */
  309.   if (cinfo->restart_interval) {
  310.     if (cinfo->restarts_to_go == 0)
  311.       emit_restart(cinfo);
  312.     cinfo->restarts_to_go--;
  313.   }
  314.  
  315.   for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
  316.     ci = cinfo->MCU_membership[blkn];
  317.     compptr = cinfo->cur_comp_info[ci];
  318.     /* Convert DC value to difference, update last_dc_val */
  319.     temp = MCU_data[blkn][0];
  320.     MCU_data[blkn][0] -= cinfo->last_dc_val[ci];
  321.     cinfo->last_dc_val[ci] = temp;
  322.     encode_one_block(MCU_data[blkn],
  323.                      cinfo->dc_huff_tbl_ptrs[compptr->dc_tbl_no],
  324.                      cinfo->ac_huff_tbl_ptrs[compptr->ac_tbl_no]);
  325.   }
  326. }
  327.  
  328.  
  329. /*
  330.  * Finish up at the end of a Huffman-compressed scan.
  331.  */
  332.  
  333. METHODDEF void
  334. huff_term (compress_info_ptr cinfo)
  335. {
  336.   /* Flush out the last data */
  337.   flush_bits();
  338.   flush_bytes();
  339.   /* Release the I/O buffer */
  340.   (*cinfo->emethods->free_small) ((void *) output_buffer);
  341. }
  342.  
  343.  
  344.  
  345.  
  346. /*
  347.  * Huffman coding optimization.
  348.  *
  349.  * This actually is optimization, in the sense that we find the best possible
  350.  * Huffman table(s) for the given data.  We first scan the supplied data and
  351.  * count the number of uses of each symbol that is to be Huffman-coded.
  352.  * (This process must agree with the code above.)  Then we build an
  353.  * optimal Huffman coding tree for the observed counts.
  354.  */
  355.  
  356. #ifdef ENTROPY_OPT_SUPPORTED
  357.  
  358.  
  359. /* These are static so htest_one_block can find 'em */
  360. static long * dc_count_ptrs[NUM_HUFF_TBLS];
  361. static long * ac_count_ptrs[NUM_HUFF_TBLS];
  362.  
  363.  
  364. LOCAL void
  365. gen_huff_coding (compress_info_ptr cinfo, HUFF_TBL *htbl, long freq[])
  366. /* Generate the optimal coding for the given counts */
  367. {
  368. #define MAX_CLEN 32             /* assumed maximum initial code length */
  369.   UINT8 bits[MAX_CLEN+1];       /* bits[k] = # of symbols with code length k */
  370.   short codesize[257];          /* codesize[k] = code length of symbol k */
  371.   short others[257];            /* next symbol in current branch of tree */
  372.   int c1, c2;
  373.   int p, i, j;
  374.   long v;
  375.  
  376.   /* This algorithm is explained in section 13.2 of JPEG-8-R8 */
  377.  
  378.   MEMZERO((void *) bits, SIZEOF(bits));
  379.   MEMZERO((void *) codesize, SIZEOF(codesize));
  380.   for (i = 0; i < 257; i++)
  381.     others[i] = -1;             /* init links to empty */
  382.   
  383.   freq[256] = 1;                /* make sure there is a nonzero count */
  384.   /* including the pseudo-symbol 256 in the Huffman procedure guarantees
  385.    * that no real symbol is given code-value of all ones, because 256
  386.    * will be placed in the largest codeword category.
  387.    */
  388.  
  389.   /* Huffman's basic algorithm to assign optimal code lengths to symbols */
  390.  
  391.   for (;;) {
  392.     /* Find the smallest nonzero frequency, set c1 = its symbol */
  393.     /* In case of ties, take the larger symbol number */
  394.     c1 = -1;
  395.     v = 1000000000L;
  396.     for (i = 0; i <= 256; i++) {
  397.       if (freq[i] && freq[i] <= v) {
  398.         v = freq[i];
  399.         c1 = i;
  400.       }
  401.     }
  402.  
  403.     /* Find the next smallest nonzero frequency, set c2 = its symbol */
  404.     /* In case of ties, take the larger symbol number */
  405.     c2 = -1;
  406.     v = 1000000000L;
  407.     for (i = 0; i <= 256; i++) {
  408.       if (freq[i] && freq[i] <= v && i != c1) {
  409.         v = freq[i];
  410.         c2 = i;
  411.       }
  412.     }
  413.  
  414.     /* Done if we've merged everything into one frequency */
  415.     if (c2 < 0)
  416.       break;
  417.     
  418.     /* Else merge the two counts/trees */
  419.     freq[c1] += freq[c2];
  420.     freq[c2] = 0;
  421.  
  422.     /* Increment the codesize of everything in c1's tree branch */
  423.     codesize[c1]++;
  424.     while (others[c1] >= 0) {
  425.       c1 = others[c1];
  426.       codesize[c1]++;
  427.     }
  428.     
  429.     others[c1] = c2;            /* chain c2 onto c1's tree branch */
  430.     
  431.     /* Increment the codesize of everything in c2's tree branch */
  432.     codesize[c2]++;
  433.     while (others[c2] >= 0) {
  434.       c2 = others[c2];
  435.       codesize[c2]++;
  436.     }
  437.   }
  438.  
  439.   /* Now count the number of symbols of each code length */
  440.   for (i = 0; i <= 256; i++) {
  441.     if (codesize[i]) {
  442.       /* The JPEG standard seems to think that this can't happen, */
  443.       /* but I'm paranoid... */
  444.       if (codesize[i] > MAX_CLEN)
  445.         ERREXIT(cinfo->emethods, "Huffman code size table overflow");
  446.  
  447.       bits[codesize[i]]++;
  448.     }
  449.   }
  450.  
  451.   /* JPEG doesn't allow symbols with code lengths over 16 bits, so if the pure
  452.    * Huffman procedure assigned any such lengths, we must adjust the coding.
  453.    * Here is what the JPEG spec says about how this next bit works:
  454.    * Since symbols are paired for the longest Huffman code, the symbols are
  455.    * removed from this length category two at a time.  The prefix for the pair
  456.    * (which is one bit shorter) is allocated to one of the pair; then,
  457.    * skipping the BITS entry for that prefix length, a code word from the next
  458.    * shortest nonzero BITS entry is converted into a prefix for two code words
  459.    * one bit longer.
  460.    */
  461.   
  462.   for (i = MAX_CLEN; i > 16; i--) {
  463.     while (bits[i] > 0) {
  464.       j = i - 2;                /* find length of new prefix to be used */
  465.       while (bits[j] == 0)
  466.         j--;
  467.       
  468.       bits[i] -= 2;             /* remove two symbols */
  469.       bits[i-1]++;              /* one goes in this length */
  470.       bits[j+1] += 2;           /* two new symbols in this length */
  471.       bits[j]--;                /* symbol of this length is now a prefix */
  472.     }
  473.   }
  474.  
  475.   /* Remove the count for the pseudo-symbol 256 from the largest codelength */
  476.   while (bits[i] == 0)          /* find largest codelength still in use */
  477.     i--;
  478.   bits[i]--;
  479.   
  480.   /* Return final symbol counts (only for lengths 0..16) */
  481.   memcpy((void *) htbl->bits, (void *) bits, SIZEOF(htbl->bits));
  482.   
  483.   /* Return a list of the symbols sorted by code length */
  484.   /* It's not real clear to me why we don't need to consider the codelength
  485.    * changes made above, but the JPEG spec seems to think this works.
  486.    */
  487.   p = 0;
  488.   for (i = 1; i <= MAX_CLEN; i++) {
  489.     for (j = 0; j <= 255; j++) {
  490.       if (codesize[j] == i) {
  491.         htbl->huffval[p] = j;
  492.         p++;
  493.       }
  494.     }
  495.   }
  496. }
  497.  
  498.  
  499. /* Process a single block's worth of coefficients */
  500. /* Note that the DC coefficient has already been converted to a difference */
  501.  
  502. LOCAL void
  503. htest_one_block (JBLOCK block, JCOEF block0,
  504.                  long dc_counts[], long ac_counts[])
  505. {
  506.   register INT32 temp;
  507.   register int nbits;
  508.   register int k, r;
  509.   
  510.   /* Encode the DC coefficient difference per section 7.3.5.1 */
  511.   
  512.   /* Find the number of bits needed for the magnitude of the coefficient */
  513.   temp = block0;
  514.   if (temp < 0) temp = -temp;
  515.   
  516.   for (nbits = 0; temp; nbits++)
  517.     temp >>= 1;
  518.   
  519.   /* Count the Huffman symbol for the number of bits */
  520.   dc_counts[nbits]++;
  521.   
  522.   /* Encode the AC coefficients per section 7.3.5.2 */
  523.   
  524.   r = 0;                        /* r = run length of zeros */
  525.   
  526.   for (k = 1; k < DCTSIZE2; k++) {
  527.     if ((temp = block[k]) == 0) {
  528.       r++;
  529.     } else {
  530.       /* if run length > 15, must emit special run-length-16 codes (0xF0) */
  531.       while (r > 15) {
  532.         ac_counts[0xF0]++;
  533.         r -= 16;
  534.       }
  535.       
  536.       /* Find the number of bits needed for the magnitude of the coefficient */
  537.       if (temp < 0) temp = -temp;
  538.       
  539.       for (nbits = 0; temp; nbits++)
  540.         temp >>= 1;
  541.       
  542.       /* Count Huffman symbol for run length / number of bits */
  543.       ac_counts[(r << 4) + nbits]++;
  544.       
  545.       r = 0;
  546.     }
  547.   }
  548.  
  549.   /* If the last coef(s) were zero, emit an end-of-block code */
  550.   if (r > 0)
  551.     ac_counts[0]++;
  552. }
  553.  
  554.  
  555.  
  556. /*
  557.  * Trial-encode one MCU's worth of Huffman-compressed coefficients.
  558.  */
  559.  
  560. LOCAL void
  561. htest_encode (compress_info_ptr cinfo, JBLOCK *MCU_data)
  562. {
  563.   short blkn, ci;
  564.   jpeg_component_info * compptr;
  565.  
  566.   /* Take care of restart intervals if needed */
  567.   if (cinfo->restart_interval) {
  568.     if (cinfo->restarts_to_go == 0) {
  569.       /* Re-initialize DC predictions to 0 */
  570.       for (ci = 0; ci < cinfo->comps_in_scan; ci++)
  571.         cinfo->last_dc_val[ci] = 0;
  572.       /* Update restart state */
  573.       cinfo->restarts_to_go = cinfo->restart_interval;
  574.     }
  575.     cinfo->restarts_to_go--;
  576.   }
  577.  
  578.   for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
  579.     ci = cinfo->MCU_membership[blkn];
  580.     compptr = cinfo->cur_comp_info[ci];
  581.     /* NB: unlike the real entropy encoder, we may not change the input data */
  582.     htest_one_block(MCU_data[blkn],
  583.                     (JCOEF) (MCU_data[blkn][0] - cinfo->last_dc_val[ci]),
  584.                     dc_count_ptrs[compptr->dc_tbl_no],
  585.                     ac_count_ptrs[compptr->ac_tbl_no]);
  586.     cinfo->last_dc_val[ci] = MCU_data[blkn][0];
  587.   }
  588. }
  589.  
  590.  
  591.  
  592. /*
  593.  * Find the best coding parameters for a Huffman-coded scan.
  594.  * When called, the scan data has already been converted to a sequence of
  595.  * MCU groups of quantized coefficients, which are stored in a "big" array.
  596.  * The source_method knows how to iterate through that array.
  597.  * On return, the MCU data is unmodified, but the Huffman tables referenced
  598.  * by the scan components may have been altered.
  599.  */
  600.  
  601. METHODDEF void
  602. huff_optimize (compress_info_ptr cinfo, MCU_output_caller_ptr source_method)
  603. /* Optimize Huffman-coding parameters (Huffman symbol table) */
  604. {
  605.   int i, tbl;
  606.   HUFF_TBL **htblptr;
  607.  
  608.   /* Allocate and zero the count tables */
  609.   /* Note that gen_huff_coding expects 257 entries in each table! */
  610.  
  611.   for (i = 0; i < NUM_HUFF_TBLS; i++) {
  612.     dc_count_ptrs[i] = NULL;
  613.     ac_count_ptrs[i] = NULL;
  614.   }
  615.  
  616.   for (i = 0; i < cinfo->comps_in_scan; i++) {
  617.     /* Create DC table */
  618.     tbl = cinfo->cur_comp_info[i]->dc_tbl_no;
  619.     if (dc_count_ptrs[tbl] == NULL) {
  620.       dc_count_ptrs[tbl] = (long *) (*cinfo->emethods->alloc_small)
  621.                                         (257 * SIZEOF(long));
  622.       MEMZERO((void *) dc_count_ptrs[tbl], 257 * SIZEOF(long));
  623.     }
  624.     /* Create AC table */
  625.     tbl = cinfo->cur_comp_info[i]->ac_tbl_no;
  626.     if (ac_count_ptrs[tbl] == NULL) {
  627.       ac_count_ptrs[tbl] = (long *) (*cinfo->emethods->alloc_small)
  628.                                         (257 * SIZEOF(long));
  629.       MEMZERO((void *) ac_count_ptrs[tbl], 257 * SIZEOF(long));
  630.     }
  631.   }
  632.  
  633.   /* Initialize DC predictions to 0 */
  634.   for (i = 0; i < cinfo->comps_in_scan; i++) {
  635.     cinfo->last_dc_val[i] = 0;
  636.   }
  637.   /* Initialize restart stuff */
  638.   cinfo->restarts_to_go = cinfo->restart_interval;
  639.  
  640.   /* Scan the MCU data, count symbol uses */
  641.   (*source_method) (cinfo, htest_encode);
  642.  
  643.   /* Now generate optimal Huffman tables */
  644.   for (tbl = 0; tbl < NUM_HUFF_TBLS; tbl++) {
  645.     if (dc_count_ptrs[tbl] != NULL) {
  646.       htblptr = & cinfo->dc_huff_tbl_ptrs[tbl];
  647.       if (*htblptr == NULL)
  648.         *htblptr = (*cinfo->emethods->alloc_small) (SIZEOF(HUFF_TBL));
  649.       /* Set sent_table FALSE so updated table will be written to JPEG file. */
  650.       (*htblptr)->sent_table = FALSE;
  651.       /* Compute the optimal Huffman encoding */
  652.       gen_huff_coding(cinfo, *htblptr, dc_count_ptrs[tbl]);
  653.       /* Release the count table */
  654.       (*cinfo->emethods->free_small) ((void *) dc_count_ptrs[tbl]);
  655.     }
  656.     if (ac_count_ptrs[tbl] != NULL) {
  657.       htblptr = & cinfo->ac_huff_tbl_ptrs[tbl];
  658.       if (*htblptr == NULL)
  659.         *htblptr = (*cinfo->emethods->alloc_small) (SIZEOF(HUFF_TBL));
  660.       /* Set sent_table FALSE so updated table will be written to JPEG file. */
  661.       (*htblptr)->sent_table = FALSE;
  662.       /* Compute the optimal Huffman encoding */
  663.       gen_huff_coding(cinfo, *htblptr, ac_count_ptrs[tbl]);
  664.       /* Release the count table */
  665.       (*cinfo->emethods->free_small) ((void *) ac_count_ptrs[tbl]);
  666.     }
  667.   }
  668. }
  669.  
  670.  
  671. #endif /* ENTROPY_OPT_SUPPORTED */
  672.  
  673.  
  674. /*
  675.  * The method selection routine for Huffman entropy encoding.
  676.  */
  677.  
  678. GLOBAL void
  679. jselchuffman (compress_info_ptr cinfo)
  680. {
  681.   if (! cinfo->arith_code) {
  682.     cinfo->methods->entropy_encoder_init = huff_init;
  683.     cinfo->methods->entropy_encode = huff_encode;
  684.     cinfo->methods->entropy_encoder_term = huff_term;
  685. #ifdef ENTROPY_OPT_SUPPORTED
  686.     cinfo->methods->entropy_optimize = huff_optimize;
  687. #endif
  688.   }
  689. }
  690.